Basic calculator IV¶
Time: VAR; Space: O(E+DT); hard*
Given an expression such as expression = “e + 8 - a + 5” and an evaluation map such as {“e”: 1} (given in terms of evalvars = [“e”] and evalints = [1]), return a list of tokens representing the simplified expression, such as [“-1*a“,”14”] * An expression alternates chunks and symbols, with a space separating each chunk and symbol. * A chunk is either an expression in parentheses, a variable, or a non-negative integer. * A variable is a string of lowercase letters (not including digits.) Note that variables can be multiple letters, and note that variables never have a leading coefficient or unary operator like “2x” or “-x”.
Expressions are evaluated in the usual order: brackets first, then multiplication, then addition and subtraction. For example, expression = “1 + 2 * 3” has an answer of [“7”].
The format of the output is as follows:
For each term of free variables with non-zero coefficient, we write the free variables within a term in sorted order lexicographically. For example, we would never write a term like “bac”, only “abc”.
Terms have degree equal to the number of free variables being multiplied, counting multiplicity. (For example, “aab*c” has degree 4.) We write the largest degree terms of our answer first, breaking ties by lexicographic order ignoring the leading coefficient of the term.
The leading coefficient of the term is placed directly to the left with an asterisk separating it from the variables (if they exist.) A leading coefficient of 1 is still printed. An example of a well formatted answer is [“-2aaa”, “3aab”, “3bb”, “4a”, “5c”, “-6”] Terms (including constant terms) with coefficient 0 are not included. For example, an expression of “0” has an output of [].
Example 1:
Input: expression = “e + 8 - a + 5”, evalvars = [“e”], evalints = [1]
Output: [“-1*a“,”14”]
Example 2:
Input: expression = “e - 8 + temperature - pressure”, evalvars = [“e”, “temperature”], evalints = [1, 12]
Output: [“-1*pressure“,”5”]
Example 3:
Input: expression = “(e + 8) * (e - 8)”, evalvars = [], evalints = []
Output: [“1 * e * e”,“-64”]
Example 4:
Input: expression = “7 - 7”, evalvars = [], evalints = []
Output: []
Example 5:
Input: expression = “a * b * c + b * a * c * 4”, evalvars = [], evalints = []
Output: [“5 * a * b * c”]
Example 6:
Input: expression = “((a - b) * (b - c) + (c - a)) * ((a - b) + (b - c) * (c - a))”, evalvars = [], evalints = []
Output: [“-1 * a * a * b * b”, “2 * a * a * b * c”, “-1 * a * a * c * c”, “1 * a * b * b * b”, ” -1 * a * b * b * c“,”-1 * a * b * c * c“,”1 * a * c * c * c“,”-1 * b * b * b * c“,”2 * b * b * c * c“,”-1 * b * c * c * c“,”2 * a * a * b“,”-2 * a * a * c“,”-2 * a * b * b“,”2 * a * c * c“,”1 * b * b * b“,”-1 * b * b * c“,”1 * b * c * c“,”-1 * c * c * c“,”-1 * a * a“,”1 * a * b“,”1 * a * c“,”-1 * b * c”]
Notes:
expression will have length in range [1, 250].
evalvars, evalints will have equal lengths in range [0, 100].
1. Polynomial Class¶
Intuition
Keep a class Poly that knows a map from a list of free variables to a coefficient, and support operations on this class.
Algorithm
Each function is straightforward individually. Let’s list the functions we use:
Poly:add(this, that) returns the result of this + that.
Poly:sub(this, that) returns the result of this - that.
Poly:mul(this, that) returns the result of this * that.
Poly:evaluate(this, evalmap) returns the polynomial after replacing all free variables with constants as specified by evalmap.
Poly:toList(this) returns the polynomial in the correct output format.
Solution::combine(left, right, symbol) returns the result of applying the binary operator represented by symbol to left and right.
Solution::make(expr) makes a new Poly represented by either the constant or free variable specified by expr.
Solution::parse(expr) parses an expression into a new Poly.
[32]:
class Poly(collections.Counter):
def __add__(self, other):
self.update(other)
return self
def __sub__(self, other):
self.update({k: -v for k, v in other.items()})
return self
def __mul__(self, other):
ans = Poly()
for k1, v1 in self.items():
for k2, v2 in other.items():
ans.update({tuple(sorted(k1 + k2)): v1 * v2})
return ans
def evaluate(self, evalmap):
ans = Poly()
for k, c in self.items():
free = []
for token in k:
if token in evalmap:
c *= evalmap[token]
else:
free.append(token)
ans[tuple(free)] += c
return ans
def to_list(self):
return ["*".join((str(v),) + k)
for k, v in sorted(self.items(),
key=lambda x: (-len(x[0]), x[0]))
if v]
class Solution1(object):
"""
Time: Let N is the length of expression and M is the length of evalvars and evalints.
With an expression like (a + b) * (c + d) * (e + f) * ... the complexity is
O(2^N + M).
Space: O(N + M).
"""
def basicCalculatorIV(self, expression, evalvars, evalints):
"""
:type expression: str
:type evalvars: List[str]
:type evalints: List[int]
:rtype: List[str]
"""
evalmap = dict(zip(evalvars, evalints))
def combine(left, right, symbol):
if symbol == '+': return left + right
if symbol == '-': return left - right
if symbol == '*': return left * right
raise
def make(expr):
ans = Poly()
if expr.isdigit():
ans.update({(): int(expr)})
else:
ans[(expr,)] += 1
return ans
def parse(expr):
bucket = []
symbols = []
i = 0
while i < len(expr):
if expr[i] == '(':
bal = 0
for j in range(i, len(expr)):
if expr[j] == '(': bal += 1
if expr[j] == ')': bal -= 1
if bal == 0: break
bucket.append(parse(expr[i+1:j]))
i = j
elif expr[i].isalnum():
for j in range(i, len(expr)):
if expr[j] == ' ':
bucket.append(make(expr[i:j]))
break
else:
bucket.append(make(expr[i:]))
i = j
elif expr[i] in '+-*':
symbols.append(expr[i])
i += 1
for i in range(len(symbols) - 1, -1, -1):
if symbols[i] == '*':
bucket[i] = combine(bucket[i], bucket.pop(i+1),
symbols.pop(i))
if not bucket: return Poly()
ans = bucket[0]
for i, symbol in enumerate(symbols, 1):
ans = combine(ans, bucket[i], symbol)
return ans
P = parse(expression).evaluate(evalmap)
return P.to_list()
[33]:
s = Solution1()
expression = "e + 8 - a + 5"
evalvars = ["e"]
evalints = [1]
assert s.basicCalculatorIV(expression, evalvars, evalints) == ["-1*a","14"]
expression = "e - 8 + temperature - pressure"
evalvars = ["e", "temperature"]
evalints = [1, 12]
assert s.basicCalculatorIV(expression, evalvars, evalints) == ["-1*pressure","5"]
expression = "(e + 8) * (e - 8)"
evalvars = []
evalints = []
assert s.basicCalculatorIV(expression, evalvars, evalints) == ["1*e*e","-64"]
expression = "7 - 7"
evalvars = []
evalints = []
assert s.basicCalculatorIV(expression, evalvars, evalints) == []
expression = "a * b * c + b * a * c * 4"
evalvars = []
evalints = []
assert s.basicCalculatorIV(expression, evalvars, evalints) == ["5*a*b*c"]
expression = "((a - b) * (b - c) + (c - a)) * ((a - b) + (b - c) * (c - a))"
evalvars = []
evalints = []
assert s.basicCalculatorIV(expression, evalvars, evalints) == [
"-1*a*a*b*b", "2*a*a*b*c", "-1*a*a*c*c", "1*a*b*b*b", "-1*a*b*b*c", "-1*a*b*c*c", "1*a*c*c*c", "-1*b*b*b*c",
"2*b*b*c*c", "-1*b*c*c*c", "2*a*a*b", "-2*a*a*c", "-2*a*b*b", "2*a*c*c", "1*b*b*b", "-1*b*b*c", "1*b*c*c",
"-1*c*c*c", "-1*a*a", "1*a*b", "1*a*c", "-1*b*c"]
[16]:
import collections
import itertools
class Poly(collections.Counter):
"""
Time: +: O(d * t), t is the number of terms,
d is the average degree of terms
-: O(d * t)
*: O(d * t^2)
eval: O(d * t)
to_list: O(d * tlogt)
Space: O(e + d * t), e is the number of evalvars
"""
def __init__(self, expr=None):
if expr is None:
return
if expr.isdigit():
self.update({(): int(expr)})
else:
self[(expr,)] += 1
def __add__(self, other):
self.update(other)
return self
def __sub__(self, other):
self.update({k: -v for k, v in other.items()})
return self
def __mul__(self, other):
def merge(k1, k2):
result = []
i, j = 0, 0
while i != len(k1) or j != len(k2):
if j == len(k2):
result.append(k1[i])
i += 1
elif i == len(k1):
result.append(k2[j])
j += 1
elif k1[i] < k2[j]:
result.append(k1[i])
i += 1
else:
result.append(k2[j])
j += 1
return result
result = Poly()
for k1, v1 in self.items():
for k2, v2 in other.items():
result.update({tuple(merge(k1, k2)): v1*v2})
return result
def eval(self, lookup):
result = Poly()
for polies, c in self.items():
key = []
for var in polies:
if var in lookup:
c *= lookup[var]
else:
key.append(var)
result[tuple(key)] += c
return result
def to_list(self):
return ["*".join((str(v),) + k)
for k, v in sorted(self.items(),
key=lambda x: (-len(x[0]), x[0]))
if v]
class Solution2(object):
def basicCalculatorIV(self, expression, evalvars, evalints):
"""
:type expression: str
:type evalvars: List[str]
:type evalints: List[int]
:rtype: List[str]
"""
def compute(operands, operators):
left, right = operands.pop(), operands.pop()
op = operators.pop()
if op == '+':
operands.append(left + right)
elif op == '-':
operands.append(left - right)
elif op == '*':
operands.append(left * right)
def parse(s):
if not s:
return Poly()
operands, operators = [], []
operand = ""
for i in reversed(range(len(s))):
if s[i].isalnum():
operand += s[i]
if i == 0 or not s[i-1].isalnum():
operands.append(Poly(operand[::-1]))
operand = ""
elif s[i] == ')' or s[i] == '*':
operators.append(s[i])
elif s[i] == '+' or s[i] == '-':
while operators and operators[-1] == '*':
compute(operands, operators)
operators.append(s[i])
elif s[i] == '(':
while operators[-1] != ')':
compute(operands, operators)
operators.pop()
while operators:
compute(operands, operators)
return operands[-1]
lookup = dict(zip(evalvars, evalints))
return parse(expression).eval(lookup).to_list()
[19]:
s = Solution2()
expression = "e + 8 - a + 5"
evalvars = ["e"]
evalints = [1]
assert s.basicCalculatorIV(expression, evalvars, evalints) == ["-1*a","14"]
expression = "e - 8 + temperature - pressure"
evalvars = ["e", "temperature"]
evalints = [1, 12]
assert s.basicCalculatorIV(expression, evalvars, evalints) == ["-1*pressure","5"]
expression = "(e + 8) * (e - 8)"
evalvars = []
evalints = []
assert s.basicCalculatorIV(expression, evalvars, evalints) == ['1*e*e', '-64']
expression = "7 - 7"
evalvars = []
evalints = []
assert s.basicCalculatorIV(expression, evalvars, evalints) == []
expression = "a * b * c + b * a * c * 4"
evalvars = []
evalints = []
assert s.basicCalculatorIV(expression, evalvars, evalints) == ["5*a*b*c"]
expression = "((a - b) * (b - c) + (c - a)) * ((a - b) + (b - c) * (c - a))"
evalvars = []
evalints = []
assert s.basicCalculatorIV(expression, evalvars, evalints) == [
"-1*a*a*b*b", "2*a*a*b*c", "-1*a*a*c*c", "1*a*b*b*b", "-1*a*b*b*c", "-1*a*b*c*c", "1*a*c*c*c", "-1*b*b*b*c",
"2*b*b*c*c", "-1*b*c*c*c", "2*a*a*b", "-2*a*a*c", "-2*a*b*b", "2*a*c*c", "1*b*b*b", "-1*b*b*c", "1*b*c*c",
"-1*c*c*c", "-1*a*a", "1*a*b", "1*a*c", "-1*b*c"]